#include <bits/stdc++.h>

#define in read<int>()
#define rep(i, x, y) for(int i = (x); i <= (y); i++)

using namespace std;

using ll = long long;
using db = double;
using pii = pair < int, int >;
using vec = vector < int >;
using veg = vector < pii >;

template < typename T > T read() {
	T x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-', ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

template < typename T > void chkmax(T &x, const T &y) { x = x > y ? x : y; }
template < typename T > void chkmin(T &x, const T &y) { x = x < y ? x : y; }

const int N = 1.5e5 + 10;
const int inf = 1e9;

struct node {
	int mx, mxx, cmx, cot; ll sum;
} val[N << 2];
int tg1[N << 2], tg2[N << 2], n;

node operator + (node a, node b) {
	node c; c.sum = a.sum + b.sum; c.mx = max(a.mx, b.mx); c.cot = 0, c.cmx = 0; c.mxx = -inf;
	for(const auto &v : { a, b }) 
		if(v.mx == c.mx) {
			chkmax(c.mxx, v.mxx); c.cmx += v.cmx; c.cot += v.cot;
		} else {
			chkmax(c.mxx, v.mx); c.cot += v.cot + v.cmx;
		} return c;
}
void pt(int x, int v1, int v2) {
	val[x].mx += v1; val[x].mxx += v2; val[x].sum += 1ll * val[x].cmx * v1 + 1ll * val[x].cot * v2;
	tg1[x] += v1; tg2[x] += v2;
}
void pd(int x) {
	if(tg1[x] || tg2[x]) {
		int tmx = max(val[x << 1].mx, val[x << 1 | 1].mx);
		pt(x << 1, (tmx == val[x << 1].mx ? tg1[x] : tg2[x]), tg2[x]);
		pt(x << 1 | 1, (tmx == val[x << 1 | 1].mx ? tg1[x] : tg2[x]), tg2[x]);
		tg1[x] = tg2[x] = 0;
	}
}
void build(int o = 1, int l = 1, int r = n) {
	tg1[o] = tg2[o] = 0; val[o].mx = 0; val[o].mxx = -inf; val[o].cmx = val[o].cot = val[o].sum = 0; if(l == r) return; int mid = l + r >> 1;
	build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r);
}
void ins(int pos, int v, int o = 1, int l = 1, int r = n) {
	if(l == r) return val[o].mx = v, val[o].cmx = 1, val[o].cot = 0, val[o].mxx = -inf, val[o].sum = v, void(); int mid = l + r >> 1; pd(o);
	if(pos <= mid) ins(pos, v, o << 1, l, mid); else ins(pos, v, o << 1 | 1, mid + 1, r);
	val[o] = val[o << 1] + val[o << 1 | 1];
}
void add(int xl, int xr, int v, int o = 1, int l = 1, int r = n) {
	if(xl == l && xr == r) return pt(o, v, v); int mid = l + r >> 1; pd(o);
	if(xr <= mid) add(xl, xr, v, o << 1, l, mid); else if(xl > mid) add(xl, xr, v, o << 1 | 1, mid + 1, r);
	else add(xl, mid, v, o << 1, l, mid), add(mid + 1, xr, v, o << 1 | 1, mid + 1, r);
	val[o] = val[o << 1] + val[o << 1 | 1];
}
void cmin(int xl, int xr, int v, int o = 1, int l = 1, int r = n) {
	if(v >= val[o].mx) return; if(xl == l && xr == r) { if(val[o].mxx <= v) return pt(o, v - val[o].mx, 0); } int mid = l + r >> 1; pd(o);
	if(xr <= mid) cmin(xl, xr, v, o << 1, l, mid); else if(xl > mid) cmin(xl, xr, v, o << 1 | 1, mid + 1, r);
	else cmin(xl, mid, v, o << 1, l, mid), cmin(mid + 1, xr, v, o << 1 | 1, mid + 1, r);
	val[o] = val[o << 1] + val[o << 1 | 1];
}
/*
void pda(int o = 1, int l = 1, int r = n) {
	if(l == r) return; pd(o); int mid = l + r >> 1;
	pda(o << 1, l, mid); pda(o << 1 | 1, mid + 1, r); val[o] = val[o << 1] + val[o << 1 | 1];
}
*/

int a[N], pos[N];
ll ans[N];

struct BIT {
	int tr[N];
	void add(int x, int v) { for(; x <= n; x += x & -x) tr[x] += v; }
	int query(int x) { int res = 0; for(; x; x -= x & -x) res += tr[x]; return res; }
	void reset() { rep(i, 1, n) tr[i] = 0; }
} T;

void solve() {
	rep(i, 1, n) pos[a[i]] = i;
	build(); T.reset();
	rep(x, 1, n) {
		int p = pos[x]; if(p < n) add(p + 1, n, 1);
		ins(p, x + 1); int v = T.query(p); if(p > 1) cmin(1, p - 1, v + 1);
		T.add(p, 1); ans[x] += val[1].sum; 
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
#endif
	n = in; rep(i, 1, n) a[i] = in;
	solve(); reverse(a + 1, a + n + 1); solve(); rep(i, 1, n) printf("%lld\n", ans[i] - 1ll * i * (i + 2));
	return 0;
}
